home *** CD-ROM | disk | FTP | other *** search
/ Aminet 24 / Aminet 24 (1998)(GTI - Schatztruhe)[!][Apr 1998].iso / Aminet / comm / mail / Mutt089src.lha / Mutt-0.89i-AMIGA / src / rx / rxsuper.c < prev    next >
C/C++ Source or Header  |  1998-01-28  |  38KB  |  1,417 lines
  1.  
  2.  
  3. /*    Copyright (C) 1995, 1996 Tom Lord
  4.  * 
  5.  * This program is free software; you can redistribute it and/or modify
  6.  * it under the terms of the GNU Library General Public License as published by
  7.  * the Free Software Foundation; either version 2, or (at your option)
  8.  * any later version.
  9.  * 
  10.  * This program is distributed in the hope that it will be useful,
  11.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  13.  * GNU Library General Public License for more details.
  14.  * 
  15.  * You should have received a copy of the GNU Library General Public License
  16.  * along with this software; see the file COPYING.  If not, write to
  17.  * the Free Software Foundation, 59 Temple Place - Suite 330, 
  18.  * Boston, MA 02111-1307, USA. 
  19.  */
  20.  
  21.  
  22.  
  23. #include "rxall.h"
  24. #include "rxsuper.h"
  25.  
  26.  
  27. /* The functions in the next several pages define the lazy-NFA-conversion used
  28.  * by matchers.  The input to this construction is an NFA such as 
  29.  * is built by compactify_nfa (rx.c).  The output is the superNFA.
  30.  */
  31.  
  32. /* Match engines can use arbitrary values for opcodes.  So, the parse tree 
  33.  * is built using instructions names (enum rx_opcode), but the superstate
  34.  * nfa is populated with mystery opcodes (void *).
  35.  *
  36.  * For convenience, here is an id table.  The opcodes are == to their inxs
  37.  *
  38.  * The lables in re_search_2 would make good values for instructions.
  39.  */
  40.  
  41. void * rx_id_instruction_table[rx_num_instructions] =
  42. {
  43.   (void *) rx_backtrack_point,
  44.   (void *) rx_do_side_effects,
  45.   (void *) rx_cache_miss,
  46.   (void *) rx_next_char,
  47.   (void *) rx_backtrack,
  48.   (void *) rx_error_inx
  49. };
  50.  
  51.  
  52.  
  53.  
  54. /* The partially instantiated superstate graph has a transition 
  55.  * table at every node.  There is one entry for every character.
  56.  * This fills in the transition for a set.
  57.  */
  58. #ifdef __STDC__
  59. static void 
  60. install_transition (struct rx_superstate *super,
  61.             struct rx_inx *answer, rx_Bitset trcset) 
  62. #else
  63. static void 
  64. install_transition (super, answer, trcset)
  65.      struct rx_superstate *super;
  66.      struct rx_inx *answer;
  67.      rx_Bitset trcset;
  68. #endif
  69. {
  70.   struct rx_inx * transitions = super->transitions;
  71.   int chr;
  72.   for (chr = 0; chr < 256; )
  73.     if (!*trcset)
  74.       {
  75.     ++trcset;
  76.     chr += 32;
  77.       }
  78.     else
  79.       {
  80.     RX_subset sub = *trcset;
  81.     RX_subset mask = 1;
  82.     int bound = chr + 32;
  83.     while (chr < bound)
  84.       {
  85.         if (sub & mask)
  86.           transitions [chr] = *answer;
  87.         ++chr;
  88.         mask <<= 1;
  89.       }
  90.     ++trcset;
  91.       }
  92. }
  93.  
  94.  
  95. #ifdef __STDC__
  96. static int
  97. qlen (struct rx_superstate * q)
  98. #else
  99. static int
  100. qlen (q)
  101.      struct rx_superstate * q;
  102. #endif
  103. {
  104.   int count = 1;
  105.   struct rx_superstate * it;
  106.   if (!q)
  107.     return 0;
  108.   for (it = q->next_recyclable; it != q; it = it->next_recyclable)
  109.     ++count;
  110.   return count;
  111. }
  112.  
  113. #ifdef __STDC__
  114. static void
  115. check_cache (struct rx_cache * cache)
  116. #else
  117. static void
  118. check_cache (cache)
  119.      struct rx_cache * cache;
  120. #endif
  121. {
  122.   struct rx_cache * you_fucked_up = 0;
  123.   int total = cache->superstates;
  124.   int semi = cache->semifree_superstates;
  125.   if (semi != qlen (cache->semifree_superstate))
  126.     check_cache (you_fucked_up);
  127.   if ((total - semi) != qlen (cache->lru_superstate))
  128.     check_cache (you_fucked_up);
  129. }
  130. #ifdef __STDC__
  131. char *
  132. rx_cache_malloc (struct rx_cache * cache, int size)
  133. #else
  134. char *
  135. rx_cache_malloc (cache, size)
  136.      struct rx_cache * cache;
  137.      int size;
  138. #endif
  139. {
  140.   char * answer;
  141.   answer = (char *)malloc (size);
  142.   if (answer)
  143.     cache->bytes_used += size;
  144.   return answer;
  145. }
  146.  
  147.  
  148. #ifdef __STDC__
  149. void
  150. rx_cache_free (struct rx_cache * cache, int size, char * mem)
  151. #else
  152. void
  153. rx_cache_free (cache, size, mem)
  154.      struct rx_cache * cache;
  155.      int size;
  156.      char * mem;
  157. #endif
  158. {
  159.   free (mem);
  160.   cache->bytes_used -= size;
  161. }
  162.  
  163.  
  164.  
  165. /* When a superstate is old and neglected, it can enter a 
  166.  * semi-free state.  A semi-free state is slated to die.
  167.  * Incoming transitions to a semi-free state are re-written
  168.  * to cause an (interpreted) fault when they are taken.
  169.  * The fault handler revives the semi-free state, patches
  170.  * incoming transitions back to normal, and continues.
  171.  *
  172.  * The idea is basicly to free in two stages, aborting 
  173.  * between the two if the state turns out to be useful again.
  174.  * When a free is aborted, the rescued superstate is placed
  175.  * in the most-favored slot to maximize the time until it
  176.  * is next semi-freed.
  177.  *
  178.  * Overall, this approximates truly freeing superstates in
  179.  * lru order, but does not involve the cost of updating perfectly 
  180.  * accurate timestamps every time a superstate is touched.
  181.  */
  182.  
  183. #ifdef __STDC__
  184. static void
  185. semifree_superstate (struct rx_cache * cache)
  186. #else
  187. static void
  188. semifree_superstate (cache)
  189.      struct rx_cache * cache;
  190. #endif
  191. {
  192.   int disqualified = cache->semifree_superstates;
  193.   if (disqualified == cache->superstates)
  194.     return;
  195.   while (cache->lru_superstate->locks)
  196.     {
  197.       cache->lru_superstate = cache->lru_superstate->next_recyclable;
  198.       ++disqualified;
  199.       if (disqualified == cache->superstates)
  200.     return;
  201.     }
  202.   {
  203.     struct rx_superstate * it = cache->lru_superstate;
  204.     it->next_recyclable->prev_recyclable = it->prev_recyclable;
  205.     it->prev_recyclable->next_recyclable = it->next_recyclable;
  206.     cache->lru_superstate = (it == it->next_recyclable
  207.                  ? 0
  208.                  : it->next_recyclable);
  209.     if (!cache->semifree_superstate)
  210.       {
  211.     cache->semifree_superstate = it;
  212.     it->next_recyclable = it;
  213.     it->prev_recyclable = it;
  214.       }
  215.     else
  216.       {
  217.     it->prev_recyclable = cache->semifree_superstate->prev_recyclable;
  218.     it->next_recyclable = cache->semifree_superstate;
  219.     it->prev_recyclable->next_recyclable = it;
  220.     it->next_recyclable->prev_recyclable = it;
  221.       }
  222.     {
  223.       struct rx_distinct_future *df;
  224.       it->is_semifree = 1;
  225.       ++cache->semifree_superstates;
  226.       df = it->transition_refs;
  227.       if (df)
  228.     {
  229.       df->prev_same_dest->next_same_dest = 0;
  230.       for (df = it->transition_refs; df; df = df->next_same_dest)
  231.         {
  232.           df->future_frame.inx = cache->instruction_table[rx_cache_miss];
  233.           df->future_frame.data = 0;
  234.           df->future_frame.data_2 = (void *) df;
  235.           /* If there are any NEXT-CHAR instruction frames that
  236.            * refer to this state, we convert them to CACHE-MISS frames.
  237.            */
  238.           if (!df->effects
  239.           && (df->edge->options->next_same_super_edge[0]
  240.               == df->edge->options))
  241.         install_transition (df->present, &df->future_frame,
  242.                     df->edge->cset);
  243.         }
  244.       df = it->transition_refs;
  245.       df->prev_same_dest->next_same_dest = df;
  246.     }
  247.     }
  248.   }
  249. }
  250.  
  251.  
  252. #ifdef __STDC__
  253. static void 
  254. refresh_semifree_superstate (struct rx_cache * cache,
  255.                  struct rx_superstate * super)
  256. #else
  257. static void 
  258. refresh_semifree_superstate (cache, super)
  259.      struct rx_cache * cache;
  260.      struct rx_superstate * super;
  261. #endif
  262. {
  263.   struct rx_distinct_future *df;
  264.  
  265.   if (super->transition_refs)
  266.     {
  267.       super->transition_refs->prev_same_dest->next_same_dest = 0; 
  268.       for (df = super->transition_refs; df; df = df->next_same_dest)
  269.     {
  270.       df->future_frame.inx = cache->instruction_table[rx_next_char];
  271.       df->future_frame.data = (void *) super->transitions;
  272.       df->future_frame.data_2 = (void *)(super->contents->is_final);
  273.       /* CACHE-MISS instruction frames that refer to this state,
  274.        * must be converted to NEXT-CHAR frames.
  275.        */
  276.       if (!df->effects
  277.           && (df->edge->options->next_same_super_edge[0]
  278.           == df->edge->options))
  279.         install_transition (df->present, &df->future_frame,
  280.                 df->edge->cset);
  281.     }
  282.       super->transition_refs->prev_same_dest->next_same_dest
  283.     = super->transition_refs;
  284.     }
  285.   if (cache->semifree_superstate == super)
  286.     cache->semifree_superstate = (super->prev_recyclable == super
  287.                   ? 0
  288.                   : super->prev_recyclable);
  289.   super->next_recyclable->prev_recyclable = super->prev_recyclable;
  290.   super->prev_recyclable->next_recyclable = super->next_recyclable;
  291.  
  292.   if (!cache->lru_superstate)
  293.     (cache->lru_superstate
  294.      = super->next_recyclable
  295.      = super->prev_recyclable
  296.      = super);
  297.   else
  298.     {
  299.       super->next_recyclable = cache->lru_superstate;
  300.       super->prev_recyclable = cache->lru_superstate->prev_recyclable;
  301.       super->next_recyclable->prev_recyclable = super;
  302.       super->prev_recyclable->next_